package 算法shiyan.动态规划;/**
 * ************************************************************************
 * 项目名称: projectweb <br>
 * 文件名称:  <br>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br>
 * 文件创建：1913040634刘世锦  <br>
 * 创建时间: 2021/5/6 <br>
 *
 * @version v1.0 <br>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br>
 * ************************************************************************
 */

import java.util.Scanner;

/**
 * @ProjectName: projectweb
 * @ClassName: 数塔
 * @Description: 请描述该类的功能
 * @Author: 1913040634刘世锦
 * @Date: 2021/5/6 20:31 .
 * @version v1.0
 */
public class 数塔 {
    public static void main(String[] args) {
        System.out.println("输入数组的层数");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d[][] = new int[n][n];
        System.out.println("输入数组元素");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i >=j) {
                    d[i][j] = sc.nextInt();
                }
            }
        }
        int result = tower(d);
    }

    public static int tower(int d[][]) {
      int h = d.length;
      int l = d[h-1].length;
      int [][]stower = new int [h][l];
        int [][] path = new int[h][l];
        //初始化
        for (int i = 0; i <l ; i++) {
           stower[h-1][i] = d[h-1][i];

        }
        for (int i = h-2; i >=0 ; i--) {
            for (int j = 0; j <=i ; j++) {
                if(stower[i+1][j] > stower[i+1][j+1] ){
                    stower[i][j] = d[i][j] +stower[i+1][j];
                    path[i][j] = j;
                }else{
                    stower[i][j] = d[i][j] +stower[i+1][j+1];
                    path[i][j] = j+1;
                }
            }
        }
        System.out.println("最大的数和为"+stower[0][0]);
        System.out.print("路径为"+d[0][0]);
     int j = path[0][0];
     for(int i = 1;i<=h-1;i++){
         System.out.print("->" + d[i][j]);
         j = path[i][j];
     }
     return stower[0][0];
    }

}